Near-optimal closed-hand Chinese Poker.

This blog post looks at closed-hand Chinese Poker, and describes a near-optimal strategy for it which is readily implementable on a computer.

Chinese Poker is a 2-4 player gambling card game where each player gets dealt thirteen cards, and then secretly arranges them into three poker hands: the “back” and “middle” of five cards each, and the “front” of three cards. The back hand must be stronger than the middle hand which must be stronger than the front hand.

Once each player has arranged their hands, everyone reveals the arrangement of their cards. Scoring is done between every pair of players. There’s different variants, but in this article we’ll assume that 1 point is scored for each of front, middle and back that beats the corresponding hand in the other player’s board, and an extra 1 point if you beat the player on more hands than you lost. This way of scoring is called 4-2 scoring because assuming no ties either one player beats the other player on all three hands (scoring 4 = 1+1+1 plus 1 for the majority), or one player beats the other player on two out of three hands (scoring 2 = 1+1-1 plus 1 for the majority).

To give an example, let’s suppose Alice and Bob are playing for $10 per point.

Alice gets dealt:

Bob gets dealt:

Without seeing each other’s hands, Alice and Bob arrange their cards into back, middle and front hands.

Alice arranges her hand like this:

Bob arranges his hand like this:

Alice beats Bob in the back hand (Ace-high flush beats King-high flush), loses to Bob in the middle hand (a pair of Queens loses to a King-high flush), and beats Bob in the front hand (a pair of Jacks beats Ten-high).

Alice wins 1 point each for front and back, loses 1 for the middle, and gains 1 for winning the majority for a total of 2 points. Bob pays Alice $20 and the hand is over.

We can see some interesting strategy: Alice chose to have a weak middle hand of a pair of Queens (which is relatively unlikely to win), which allowed her to put a pair of Jacks in the front (which is relatively likely to win there). This paid off for her, allowing her to make a profit with an overall weak hand.

Optimal Counter-Strategy

For a given opponent (with a known strategy) we can find the best counter-strategy. Suppose Alice has been dealt her hand and wants to arrange them to maximize her expected value against Bob. She can mentally deal out many potential hands for Bob and see how he plays them (which she can do because she has perfect knowledge of Bob’s strategy). Then she can pick the arrangement of her own cards to score as high (on average) as possible. Apart from the large amount of computation this entails, it’s relatively simple to implement.

In practice, we don’t know our opponent’s strategy, but we can use this idea as a way to bootstrap a strategy that plays well. The obvious idea is to start with some strategy, construct it’s optimal counter-strategy, then the optimal counter-counter-strategy and so on. If $S_0$ is an initial strategy and $C(S)$ is its optimal counter-strategy then we can construct a sequence of (hopefully improving) strategies like this:

$$S_n = C(S_{n-1})$$

In general this doesn’t work because strategies tend to oscillate. For example, if we try to learn to play optimal rock-paper-scissors and start with the strategy of “always play rock”, then the optimal counter-strategy is “always play paper”, and the optimal counter-counter-strategy is “always play scissors”, and the optimal counter-counter-counter-strategy is back to “always play rock”. A fix to this is to use a blended strategy.

$$S_n = \mathrm{blend}(C(S_{n-1}), S_{n-1})$$

One interpretation is to blend the strategies by non-deterministically choosing between them for each decision. This (for specific weights of the non-deterministic choice) was proven to converge to an optimal strategy in An iterative method of solving a game, Julia Robinson (1950).

The approach I’ll take will be similar but not identical to that idea, but the result will be the same: the sequence will converge to a near-optimal (only slightly exploitable) strategy.

Parameterizing the Strategy

To define our strategy, we’ll define a scoring function that takes a triple (front, middle, back) of hands and returns an expected value. Our computer player, given a hand of 13 cards, will then pick the arrangement that maximizes the score.

Since there’s a lot of triples of hands, I tried an experiment of factoring the scoring algorithm into three parts. The idea here is to estimate a probability that each part of the hand would win independently of the other parts of the hand. For example, a strategy might think AA2 in the front has 95% chance of winning against a good opponent. Then, given the three probabilities $p_f, p_m, p_b$ which correspond to the probabilities that the front, middle and back hands win, the program can compute the expectation for the score. I was surprised to find that there’s relatively few unique hands: for the 5-card middle and back hands there’s only 6785 different hands if we treat hands the same that can never be matched against each other (for example AAAKQ and AAA32 are considered equal, because if one player has three aces, no other player can). The 3-card front hand has (obviously) even fewer unique hands. This experiment looks tempting from a practical standpoint: a strategy can be specified with around 15,000 parameters, and the blending of strategies needed for training can be done by averaging the parameters.

How should we compute the expectation for the score given the three probabilities? The part of the score that corresponds to the score for winning the front, middle and back hands are easy: it’s just the sum of the expectations for each part of the hand independently, which since the scores are all one, is the probability of winning minus the probability of losing. Writing $q_f$, $q_m$ and $q_b$ as the complements of the $p$s, that is, $q_f = 1-p_f, q_m = 1-p_m$ and $q_b = 1-p_b$ we get:

$$ E_\mathrm{base} = (p_f-q_f) + (p_m-q_m) + (p_b-q_b) $$

The bonus of 1 for winning the majority is a bit trickier. We assume that the three probabilities are independent, and that the probability of a tie is zero. The probability of winning the bonus is, by the inclusion-exclusion principle:

$$ P_\mathrm{win\ bonus} = p_fp_m + p_fp_b + p_mp_b - 2p_fp_mp_b $$

The probability of losing the bonus is similar, with $q$s instead of $p$s:

$$ P_\mathrm{lose\ bonus} = q_fq_m + q_fq_b + q_mq_b - 2q_fq_mq_b $$

Since the bonus scores one point, the expectation for the bonus is $P_\mathrm{win\ bonus} - P_\mathrm{lose\ bonus}$ and our expectation for the hand is:

$$ E = E_\mathrm{base} + P_\mathrm{win\ bonus} - P_\mathrm{lose\ bonus}$$

Since we just care about maximizing $E$ we can note that the game is zero sum and we only need to maximize the positive parts of the score:

$$ E_+ = p_f + p_b + p_m + p_fp_m + p_fp_b + p_mp_b - 2p_fp_mp_b $$.

(Proof: $E = E_+ - (4 - E_+)$)

I’ll do a calculation as an example. Let’s say we’ve estimated our front hand has 40% chance of winning, our middle as 90% and our back as 10%.

The front hand will give us 1 point 40% of the time and -1 point 60% of the time, so on average will net us 0.4 - 0.6 = -0.2 points. Similarly our middle will net us 0.9 - 0.1 = 0.8 on average and our back 0.1 - 0.9 = -0.8.

The probability of winning the bonus is $0.4\times 0.9 + 0.4\times 0.1 + 0.9 \times 0.1 - 2\times 0.4\times 0.9\times 0.1 = 0.418$.

The probability of losing the bonus is $0.6\times 0.1 + 0.6\times 0.9 + 0.1 \times 0.9 - 2\times 0.6\times 0.1\times 0.9 = 0.582$.

Our overall expectation (as estimated by these probabilities and ignoring the simplifications) for the hand is: -0.2 + 0.8 - 0.8 + 0.418 - 0.582 = -0.634.

We’ll look next at the results of training the strategy, and conclude by checking that the simplifications and assumptions made haven’t introduced serious weaknesses.

The near-optimal strategy

After training for around 20 iterations of blending with an optimal counter-strategy, the strategy converged.

To recap the strategy: pick the arrangement of cards that maximizes:

$$ E_+ = p_f + p_m + p_b + p_fp_m + p_fp_b + p_mp_b - 2p_fp_mp_b $$

where the probabilities $p_f, p_m$ and $p_b$ looked up in the appropriate table for the front, middle and back hands.

Rather than include here the full tables of numbers, I’ve summarized the data below. A fuller version can be found here and the complete strategy here.

The tables here show a hand range and the corresponding range of probabilities of winning. For example, you can read that a flush has between 91.11 and 99.28 percent chance of winning in the middle (depending on how good the flush is), and between 36.12 and 65.37 percent in the back. Given a specific hand, say a AQT82 flush in the back, we can see it has somewhere between 57.71 and 60.84 percent chance of winning. By checking the more complete table , which has entries roughly for every one percent of difference, we can narrow that down to between 59 and 60 percent or the complete table to get the exact figure: 59.64 percent.

It’s interesting to see that any full house in the middle is an extremely strong hand, and that the high cards in a flush or full house in the back make a huge difference, with both of those ranks having a 30 percent spread of winning probabilities. Similarly, no matter what your front hand (except for the rare three of a kind), high cards really matter.

Going back to the hand Alice played in the introduction:

We can use the tables here to rate the back hand as having between 60 and 66 percent chance of winning, the middle hand between 16 and 21 percent, and the front as between 72 and 78 percent. Or we can use the more complete table to get better estimates: the back hand has a 61 percent chance of winning, the middle hand 17 percent and the front hand 74 percent.

Is the strategy any good?

The strategy was created using many simplifications, the greatest of which was treating the three parts of the hand independently. We shouldn’t expect that it’s a good strategy. But it is!

To find out just how good or bad the strategy is, I ran an experiment against its optimal counter-strategy. Given a hand, the optimal counter-strategy dealt out 10,000 hands from the cards from the rest of the deck and considered how each one would be played. Then it found the way of arranging its own cards to maximize its expectation.

Then, 10,000 pairs of hands were played both ways round (that is, duplicated, to help minimize the luck of one player getting on average better cards than the other).

Much of the time (approximately 78 percent, but the exact figures are below) the trained strategy and its optimal counterpart played hands in exactly the same way. Here’s one hand which they played significantly differently:

The trained strategy played:

In duplicate, the counter-strategy played the same hand this way:

In this case, the difference made no difference in score: the opposing hand both times contained an Ace-high flush in the back, a pair of Aces in the middle, and a pair of Queens in the front.

After a couple of day’s computation, the final results of the simulation were as follows:

That means, according to this simulation, the strategy is almost optimal, losing 0.0068 points per hand against an optimally exploitative counter-strategy. It’s interesting to see that the strategy won the maximum 4 points more often than the counter-strategy, but that difference is probably just noise.

Human play

Memorizing even the coarse probability tables would help get a good feeling for how strong a hand is. For example, knowing there’s a huge (30 percent) difference between a bad flush and a good flush in the back is useful.

But is it feasible to go further and learn to play this strategy? I don’t know, but if I were to try, I’d start by learning to estimate the individual probabilities to within a percentage point. Then in play, I’d try to narrow the hand choices down to 2 or 3 possibilies, and then mentally score each one. There’s a shortcut available, namely to ignore negative scores since the game is zero-sum. That yields the difficult but doable mental calculation using percentages $P_f, P_m$ and $P_b$:

$$P_f + P_m + P_b + P_fP_m/100 + P_fP_b/100 + P_mP_b/100 - 2P_fP_mP_b/1000$$

Source Code

The go source code for the above article has been open-sourced. It can be downloaded at https://github.com/paulhankin/cpoker, or should work if you

go get github.com/paulhankin/cpoker

The code has been slightly modified since publishing; it no longer merges equivalent hands. This makes no practical difference, but there may be small numerical differences if you run the code yourself.

Attribution

Thanks for Chris Aguilar for providing card images under the LGPL. The images have been modified and manipulated slightly for this article, so imperfections are probably due to me rather than him.

Vectorized Playing Cards 2.0 — http://sourceforge.net/projects/vector-cards/
Copyright 2015 — Chris Aguilar — conjurenation@gmail.com
Licensed under LGPL 3 — http://www.gnu.org/copyleft/lesser.html